class Solution {
public:
    int canCompleteCircuit(vector<int>& g, vector<int>& c) {
        // 贪心解法
        // 统计每到一个站点时的剩余油量，如果为负数，说明起始站点无法绕环一圈
        int startIdx = 0, curSum = 0, totalSum = 0, n = g.size();
        for(int i = 0; i < n; i++)
        {
            curSum += (g[i] - c[i]);
            totalSum += (g[i] - c[i]);  // 计算所有站点剩余油量之和，如果最终为负数，说明无法到达

            if(curSum < 0)
            {
                startIdx = i + 1;
                curSum = 0;
            }                      
        }
        if(totalSum < 0)
            return -1;
        else
            return startIdx;


        // 下面这种是我自己写的暴力解法，通过不了
        // int n = c.size(), minIdx = 0x3f3f3f3f;
        // for(int i = 0; i < n; i++)
        // {
        //     int gas = 0, step = i;
        //     for(int j = 0; j < n; j++)
        //     {
        //         gas += g[step] - c[step];
        //         step = (step + 1) % n;
        //         if(gas < 0)
        //             break;
        //     }
        //     if(gas >= 0)
        //         return i;
        // }
        // return -1;
    }
};